// 450. 删除二叉搜索树中的节点

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
/* 
    思路:
        root 为空 代表搜索到值为key的节点 返回空
        root.val > key 表示值为key的节点可能存在于root的左子树中
        root.val < right 表示值为key的节点可能存在于root的右子树中
        root.value === key 
        即 root 为需要删除的节点 此时要做的就是删除root并将它的子树合成一颗子树
        保持有序，并返回根节点，根据root的子树情况分类讨论


        root 为叶子节点，没有子树此时可以直接将它删除，即返回为空
        root只有左子树，没有右子树 此时可以将它的左子树作为新的子树，返回它的左子节点
        root只有右子树，没有左子树此时可以将它的右子树作为新的子树，返回它的右子节点
        root有左右子树，这时可以将root的后继节点(比root大的最小节点，即它的右子树中的最小节点，记为successor)作为
        新的根节点代替root 并将successor从root的右子树中删除，使得在保持有序性的情况下合并左右子树


    递归
 */
var deleteNode = function (root, key) {
	if (!root) return null
	if (root.val > key) {
		root.left = deleteNode(root.left, key)
		return root
	}
	if (root.val < key) {
		root.right = deleteNode(root.right, key)
		return root
	}
	if (root.val === key) {
		if (!root.left && !root.right) return null
		if (!root.right) return root.left
		if (!root.left) return root.right
		/* 找到比root大的最小节点 */
		let successor = root.right
		while (successor.left) {
			successor = successor.left
		}
		root.right = deleteNode(root.right, successor.val)
		successor.right = root.right
		successor.left = root.left

		return successor
	}
}
